package offer.tree;

import java.util.ArrayList;

/**
 * @author DengYuan2
 * @create 2021-02-28 19:56
 */
public class n_34 {
    public static void main(String[] args) {
        n_34 n = new n_34();
        TreeNode t1 = new TreeNode(10);
        TreeNode t2 = new TreeNode(5);
        TreeNode t3 = new TreeNode(12);
        TreeNode t4 = new TreeNode(4);
        TreeNode t5 = new TreeNode(7);
        t1.left=t2;
        t1.right=t3;
        t2.left=t4;
        t2.right=t5;
        ArrayList<ArrayList<Integer>> res = n.FindPath2(t1, 22);
        System.out.println(res);

    }

    ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
        if (root==null){
            return list;
        }
        helper(new ArrayList<>(),root,target);
        return list;
    }

    public void helper(ArrayList<Integer> tmp,TreeNode root,int target){
        if (root==null){
            return;
        }
        tmp.add(root.val);
        int cur = target-root.val;
        if (cur==0 && root.left==null && root.right==null){
                list.add(new ArrayList<>(tmp));
        }else {
            helper(tmp,root.left,cur);
            helper(tmp,root.right,cur);
        }
        tmp.remove(tmp.size()-1);
    }


    ArrayList ret =  new ArrayList<ArrayList<Integer>>();
    public ArrayList<ArrayList<Integer>> FindPath2(TreeNode root,int target) {
        if (root==null){
            return ret;
        }
        getResult(root,target,new ArrayList<Integer>());
        return ret;
    }

    public void getResult(TreeNode node,int target,ArrayList<Integer> list){
        if (node==null){
            return;
        }
        if (node.left==null&&node.right==null){
            if (node.val==target){
                list.add(node.val);
                ret.add(list);
                return;
            }
        }
        int val = node.val;
        list.add(val);
        ArrayList<Integer> arrayList1 = new ArrayList<>();
        arrayList1.addAll(list);
        ArrayList<Integer> arrayList2 = new ArrayList<>();
        arrayList2.addAll(list);
        getResult(node.left,target-val,arrayList1);
        getResult(node.right,target-val,arrayList2);

    }


}
